package com.clstu.leetcode;

import java.util.*;

/**
 *leetCode题
 */
public class Solution {
    public static void main(String[] args) {
        //测试数独
//        int arr[][] = {{5, 3, 0, 0, 7, 0, 0, 0, 0},
//                {6, 0, 0, 1, 9, 5, 0, 0, 0},
//                {0, 9, 8, 0, 0, 0, 0, 6, 0},
//                {8, 0, 0, 0, 6, 0, 0, 0, 3},
//                {4, 0, 0, 8, 0, 3, 0, 0, 1},
//                {7, 0, 0, 0, 2, 0, 0, 0, 6},
//                {0, 6, 0, 0, 0, 0, 2, 8, 0},
//                {0, 0, 0, 4, 1, 9, 0, 0, 5},
//                {0, 0, 0, 0, 8, 0, 0, 7, 9}};
//        System.out.println(isValidSudoku(arr));

//        //测试赶趟
//        int[] time= new int[100000];
//        for (int i = 0; i < time.length; i++) {
//            time[i]=1;
//        }
//        System.out.println(minimumTime(time,10000000));

//        //测试字符串扫描
//        System.out.println(myAtoi("9223372036854775808"));

        //测试搜索二叉树
//        System.out.println(isValidBST(new TreeNode(0)));
//        new HashSet<>().
//        System.out.println(serialize(new TreeNode(0)));

        //测试打印折痕
        printOrder(1,3,true);
    }

    //判断9*9的数独是否有效,每行每列不能重复,每个划分好的九宫格也不能重复
    public static boolean isValidSudoku(int[][] board) {
        //判断在每一行是否只出现一次
        for (int i = 0; i < board.length; i++) {
            //思路:将一行的元素都加入到set集合,如果添加失败,说明有重复
            Set set = new HashSet<>();
            for (int j = 0; j < board[i].length; j++) {
                //如果是空格,不用理会
                if (board[i][j] == 0) {
                    continue;
                }
                if (!set.add(board[i][j])) {
                    return false;
                }
            }
        }
        //判断是否在每一列是否只出现一次
        for (int i = 0; i < board.length; i++) {
            //思路:将一行的元素都加入到set集合,如果添加失败,说明有重复
            Set set = new HashSet<>();
            for (int j = 0; j < board[i].length; j++) {
                //如果是空格,不用理会
                if (board[j][i] == 0) {
                    continue;
                }
                if (!set.add(board[j][i])) {
                    return false;
                }
            }
        }
        //判断是否在每一个九宫格不重复
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                //用集合能否加入判断
                Set set = new HashSet<>();
                for (int k = i * 3; k < i * 3 + 3; k++) {
                    for (int x = j * 3; x < j * 3 + 3; x++) {
                        //如果是空格,不理会
                        if (board[k][x] == 0) continue;
                        if (!set.add(board[k][x])) {
                            return false;
                        }
                    }
                }
            }
        }
        //如果都没有失败,说明成功
        return true;
    }

    //计算达到赶趟次数的最小时间
    public static long minimumTime(int[] time, int totalTrips) {
        Arrays.sort(time);
        //得到查找范围
        long left = 0;
        long right = (long) time[0] * totalTrips;
        long mid=0;
        //二分查找
        while (true) {
            //如果查找到最后
            if (left > right) {
                break;
            }
            System.out.println("left="+left+"  right="+right+"  count="+getTripsByTime(time,mid));
            mid = (left + right) / 2;
            //二分查找
            if (getTripsByTime(time, mid) >= totalTrips) {
                //如果时间给多了
                right = mid-1;
            }else if (getTripsByTime(time, mid) < totalTrips) {
                //如果时间给少了
                left = mid + 1;
            }
        }
        //最后得到的有效时间跟正确时间相差很小
        //右查询
        for (;; mid++) {
//            System.out.println("hello======================="+mid);
            if (getTripsByTime(time,mid)>totalTrips) break;
        }
        //左查询
        for (;;mid--) {
            if(getTripsByTime(time,mid-1)<totalTrips) break;
        }
        return mid;
    }
    //定义方法根据传入的时间(pass)得到可以走最多多少趟
    public static long getTripsByTime ( int[] time, long pass){
        long count = 0;
        for (int i = 0; i < time.length; i++) {
            count += pass / time[i];
        }
        return count;
    }

    //将传入的字符串转换成数字,注意正负和忽略前导空格已及越界情况,如果越界直接返回最大/最小值
    public static int myAtoi(String s) {
        //定义一个index反复扫描字符串,按照要求来即可
        //1.忽略前导空格
        int index =0;
        while(true){
//            System.out.println("hh");
            //如果越界
            if (index>=s.length()){
                return 0;
            }
            //如果满足条件
            if(s.charAt(index)!=' '){
                break;
            }
            //否则index后移
            index++;
        }
        //2.扫描正负号
        char singn = s.charAt(index);
        if(singn=='+'||singn=='-'){
            //如果有符号,指针右移
            index++;
        }
        //3.扫描数字,累加得到结果
        long res = 0;
        int n = 0;
        while(true){
            //如果扫描完
            if(index>=s.length()){
                break;
            }
            //如果超出范围
            if(res>Integer.MAX_VALUE){
                break;
            }
            n=s.charAt(index)-48;
            //如果扫描到非数字
            if(n<0||n>9){
                break;
            }
            res = res*10+n;
            //指针后移
            index++;
        }
        //如果超出了范围,截断处理的意思就是直接返回最大值或最小值
        if(res>Integer.MAX_VALUE){
            return singn=='-'?Integer.MIN_VALUE:Integer.MAX_VALUE;
        }
        if(singn=='-'){
            res = -res;
        }
        return (int)res;
    }

    public static TreeNode pre=null;
    //判断是否是二叉排序树
    public static boolean isValidBST(TreeNode root) {
        //思路分析:
        //如果是搜索二叉树,在中序遍历的时候一定是升序的
        //于是,采用中序遍历的方式
        //可以用一个全局变量来记录前一个节点,如果大于当前节点,则返回false
        //中序遍历 左边 ---> 自己 ---> 右边
        //先判断是否不用判断
        if(root == null){
            return true;
        }
        //左递归
        if(root.left!=null && !isValidBST(root.left)){
            return false;
        }
        //自己
        if(pre != null){
            if(pre.val>root.val){
                return false;
            }
        }
        //右递归
        if(root.right!=null && !isValidBST(root.left)){
            return false;
        }
        //pre的值后移
        pre = root;
        //如果没有失败,说明是搜索二叉树
        return true;
    }

    //判断括号是否匹配
    public boolean isValid(String s) {
        //思路分析:可以用栈结构来解决
        //1.如果是左括号,直接入栈
        //2.如果是右括号,弹出栈顶看是否匹配,匹配则消掉一对括号
        //,不匹配直接返回false
        Stack<Character> s1 = new Stack();

        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            //做括号直接入栈
            if(c=='('||c=='{'||c=='['){
                s1.push(c);
            }
            //右括号就弹出再比较
            if(c==')'||c=='}'||c==']'){
                char c2 = s1.pop();
                //如果不匹配
                if(!(c==')'&&c2=='(' || c=='}'&&c2=='{' || c==']'&&c2=='[')){
                    return false;
                }
            }
        }
        //如果没有失败
        return s1.isEmpty();
    }

    //序列化
    public static String serialize(TreeNode root) {
        //思路分析:
        //序列化的顺序是层次遍历顺序,如果没有节点就是null
        StringBuilder resStr = new StringBuilder("[");
        //先层次遍历把所有的节点放入ArrayList
        List<TreeNode> vals = new ArrayList<>();
        //1.跟节点入队列
        vals.add(root);
        //层序遍历
        TreeNode cur = null;
        //还需要判别再哪一层
        int i = 0;
        while(true){
            System.out.println("hell");
            //如果遍历完
            if(i >= vals.size()){
                break;
            }
            //弹出处理
            cur = vals.get(i);
            //如果是空
            if(cur == null){
                i++;
                continue;
            }
            //左右节点入队列
            vals.add(cur.left);
            vals.add(cur.right);
            //指针后移
            i++;
        }
        //统计有效节点的个数
        i = 0;
        int valSize = 0;
        while(i<vals.size()){
            if(vals.get(i)!=null) valSize = i+1;
            i++;
        }
        //拼接字符串
        for(int j=0;j<valSize-1;j++){
            cur = vals.get(j);
            //如果为空
            if(cur == null){
                resStr.append("null,");
            }else{
                //不为空
                resStr.append(cur.val).append(",");
            }
        }
        //拼接最后一个
        resStr.append(vals.get(valSize - 1).val).append("]");
        return resStr.toString();
    }

    //题目:一直对着纸条N次,输出纸条上的序列(凹,凸....)
    //i表示这是第几次折这张纸,便于递归调用越界返回
    //N表示总共需要折多少次
    //down表示本次要打印的是凹折痕还是凸折痕
    private static int count = 0;
    public static void printOrder(int i,int N,boolean down){
        //思路分析:
        //有这样一个规律.每次对这后,上一次折痕的上面一条折痕一定是凹折痕,
        //                     上一次折痕的下面一条折痕一定是凸折痕.
        //于是可以用一颗想象的二叉树中序遍历输出这个序列
        //如果超过最大对着次数
        if (i > N) {
            return ;
        }
        //打印上面的折痕(凹)
        printOrder(i+1,N,true);
        //打印自己
        System.out.println(down?i+"凹 ":i+"凸 ");
        //打印下面(凸)
        printOrder(i+1,N,false);
    }
}

/**
 * 二叉树节点类
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }

    //编写方法添加节点,从左到右的次序依次添加
    public void add(TreeNode node){
        //添加到左边
        if(left == null){
            left = node;
            return;
        }
        //添加到右边
        if(right == null){
            right = node;
            return;
        }
        //根据左右的高度添加,优先添加左边
        if(getHeight(left)<getHeight(right)){
            left.add(node);
        }else {
            right.add(node);
        }
    }

    //编写方法,判断传入节点为根节点的子树的深度
    public int getHeight(TreeNode node){
        return Math.max(node.left==null?0:getHeight(node.left),node.right==null?0:getHeight(node.right))+1;
    }
}


